package come.homework;

import javax.swing.tree.TreeNode;
import java.util.HashMap;
import java.util.Map;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: ws
 * Date: 2023-01-11
 * Time: 22:14
 */
public class Test1 {
}

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
//https://leetcode.cn/problems/construct-binary-tree-from-preorder-and-inorder-traversal/submissions/394650627/
//仿照后续和中序的解法
    //迭代法！！！！！题解
class Solution {
    int[] preorder;
    int[] inorder;
    int pre_idx;
    Map<Integer, Integer> map = new HashMap<>();

    private TreeNode helper(int in_left, int in_right) {
        if (in_left > in_right) {
            return null;
        }
        int root_val = preorder[pre_idx];
        int index = map.get(root_val);
        pre_idx++;
        TreeNode root = new TreeNode(root_val);
        root.left = helper(in_left, index - 1);
        root.right = helper(index + 1, in_right);
        return root;
    }


    public TreeNode buildTree(int[] preorder, int[] inorder) {
        this.preorder = preorder;
        this.inorder = inorder;
        pre_idx = 0;
        int index = 0;
        for (Integer val : inorder) {
            map.put(val, index++);
        }
        return helper(0, inorder.length - 1);
    }
}